#include <stdio.h>
#include <assert.h>
#include <iostream>
using namespace std;


//模拟实现list(双向带头节点链表)


//定义一个List节点
template<class T>
struct ListNode
{
  ListNode *_next;
  ListNode *_prev;
  T _data;
  ListNode(const T & val=T()):_data(val),_next(NULL),_prev(NULL)
  {}
};




template<class T,class Ref ,class Ptr>
struct MyIterator
{
    typedef ListNode<T> Node;
    MyIterator(Node *_Head):_node(_Head)
    {}

    //注意，迭代器只是为了访问容器，这里不能写析构
    
    //也不需要写拷贝构造，这里需要的是浅拷贝，使用默认的
    Ref operator*()
    {
      return _node->_data;
    }

    Ptr operator->()
    {
      return _node;
    }


    //这里的返回值用迭代器接收是因为，但参数的构造函数支持类型转化
     MyIterator operator++()//前置++
    {
      _node=_node->_next;
      return _node;
    }

     MyIterator operator++(int)//后置++
     {
       Node *tmp=_node;
       _node=_node->_next;
        return tmp;
     }
    
     MyIterator operator--()//前置--
     {
        _node=_node->_prev;
        return _node;
     }

     MyIterator operator --(int)//后置--
     {
        Node *tmp=_node;
        _node=_node->_prev;
        return tmp;
     }

     bool operator==(const MyIterator& it )const
     {
        return it._node==_node; 
     }

     bool operator!=(const MyIterator& it)const
     {
       return it._node!=_node;
     }

    Node *_node;

};

template<class T>
class MyList
{
  public:
    typedef ListNode<T> Node;
    typedef MyIterator<T,T&,T*> Iterator;
    typedef MyIterator<T,const T&,const T*> const_Iterator;

    MyList():_Head(new Node())
  {
    _Head->_next=_Head;
    _Head->_prev=_Head;
  }

    ~MyList()
    { 
      delete _Head;
    }

    Iterator begin()
    {
      return _Head->_next;
    }

    Iterator end()
    {
      return _Head;
    }

    //const版本
    const_Iterator begin()const 
    {
      return const_Iterator(_Head->_next);
    }

    const_Iterator end() const
    {
      return const_Iterator(_Head);
    }

    Iterator Insert(const Iterator& pos,const T & val )
    {
      //这里不用判断pos位置是否合法

      Node *new_node=new Node(val);

      Node *cur=pos._node;//拿出迭代器中的node
      
      Node *pre=cur->_prev;
      Node *next=cur;
      //pre cur next
      
      new_node->_next=next;
      next->_prev=new_node;

      pre->_next=new_node;
      new_node->_prev=pre;

      return pos;
    }

    Iterator Erase(const Iterator & pos)
    {
      assert(pos!=Iterator(_Head));
      //这里判断pos位置合法应该是 不为Head就可以
      if(_Head->_next==_Head)
      {
        return Iterator(_Head);
      }
      
      Node *cur=pos._node;
      Node *pre=cur->_prev;
      Node *next=cur->_next;

      pre->_next=next;
      next->_prev=pre;

      delete cur;
      return Iterator(next);
      
    }

    void PushFront(const  T& val)
    {
      Insert(begin(),val);
    }

    void PopFront()
    {
      Erase(begin());
    }

    void PushBack(const T & val)
    {
      Insert(--end(),val);
    }

    void PopBack()
    {
      Erase(--end());
    }
    
  protected:
    Node *_Head;
};
